using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;

namespace Nate.Pathfinding
{
    // (With Edge Relaxation)
    public class Dijkstras : Pathfinding.IPathfind
    {
        // 
        // Public Methods 
        //

        public void Init(NodeID start_id, NodeID dest_id, Graph graph)
        {
            _success        = false;
            _graph          = graph;
            _source         = start_id.GraphIndex;
            _destination    = dest_id.GraphIndex;

            _cost_to_this_node = NUtils.Array.AllocateWithDefault<double>(_graph.Nodes.Count, double.MaxValue);

            _shortest_path_tree = new Edge[_graph.Nodes.Count];
            _search_frontier = new Edge[_graph.Nodes.Count];
            
            _queue = new NUtils.PriorityQueue<Node>(_graph.Nodes.Count, _CompareNodes);
            _queue.Insert(_graph.Nodes[_source]);
        }

        public Shared.Status Tick()
        {
            if (_success)
            {
                return Shared.Status.Success;
            }

            return _tick();
        }

        // 
        // Public Properties 
        //

        public List<Point> Path
        {
            get
            {
                List<Point> points = new List<Point>();

                if (_success)
                {
                    int i = _destination;
                    while (i != _source)
                    {
                        points.Add(_graph.Nodes[i].Point);

                        Edge e = _shortest_path_tree[i];
                        if (null == e)
                        {
                            break;
                        }

                        i = e.Other(i);
                    }

                    points.Reverse();
                }
                else
                {
                    // Let the caller see the nodes that we've visited.

                    foreach (Edge e in _shortest_path_tree)
                    {
                        if (null == e)
                        {
                            continue;
                        }

                        points.Add(_graph.Nodes[e.A].Point);
                        points.Add(_graph.Nodes[e.B].Point);
                    }
                }

                return points;
            }
        }

        public Nate.Shared.Utils.Options Options
        {
            get
            {
                return null;
            }
        }

        public string OptionSelection
        {
            set
            {
            }
        }
        
        // 
        // Private Data
        //

        private bool                        _success;
        private int                         _source;
        private int                         _destination;
        private Graph                       _graph;
        private Edge[]                      _shortest_path_tree;
        private Edge[]                      _search_frontier;
        private double[]                    _cost_to_this_node;
        private NUtils.PriorityQueue<Node>  _queue;

        //
        // Private Methods
        //

        private Shared.Status _tick()
        {
            Node next_best = _queue.Dequeue();
            int next_index = next_best.Index;

            _shortest_path_tree[next_index] = _search_frontier[next_index];

            if (_destination == next_index)
            {
                _success = true;
                return Shared.Status.Success;
            }

            foreach (Edge e in next_best.Edges)
            {
                double new_cost = _cost_to_this_node[next_index] + e.Cost;
                int to_node = e.Other(next_index);

                if (null == _search_frontier[to_node])
                {
                    _cost_to_this_node[to_node] = new_cost;
                    _search_frontier[to_node] = e;
                    _queue.Insert(_graph.Nodes[to_node]);
                }
                else if (new_cost < _cost_to_this_node[to_node] &&
                         null == _shortest_path_tree[to_node])
                {
                    _cost_to_this_node[to_node] = new_cost;
                    _search_frontier[to_node] = e;
                    _queue.PriorityChanged();
                }
            }

            return Shared.Status.InProcess;
        }

        private int _CompareNodes(Node a, Node b)
        {
            double cost_a = _cost_to_this_node[a.Index];
            double cost_b = _cost_to_this_node[b.Index];
            return cost_a.CompareTo(cost_b);
        }
    }
}
